package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * author: shalock.lin
 * date: 2022/11/13
 * describe:
 */
public class Main {

    public static void main(String[] args) {

    }

    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    public int lengthOfLongestSubstring(String s) {
        int len = s.length(), left = 0, right = 0, maxLen = 0;
        char[] array  = s.toCharArray();
        Map<Character, Integer> dataMap = new HashMap<Character, Integer>();
        while (right < len) {
            char c = array[right];
            right++;
            dataMap.put(c, dataMap.getOrDefault(c,0)+1);
            while (dataMap.getOrDefault(c,0) > 1) {
                char d = array[left];
                left++;
                dataMap.put(d, dataMap.getOrDefault(d, 0)-1);
            }
            maxLen = Math.max(maxLen, right-left);
        }
        return maxLen;
    }

    /**
     209. 长度最小的子数组
     给定一个含有 n 个正整数的数组和一个正整数 target 。
     找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     */
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length, left = 0, right = 0, minLen = 0, curSum = 0;
        while (right < len) {
            curSum = curSum+nums[right];
            while (curSum >= target) {
                if (right-left+1 < minLen || minLen == 0) {
                    minLen = right-left+1;
                }
                curSum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen;
    }
}
